package pers.qianyu.month_202012.date_20201223;

import org.junit.*;

import java.util.*;

/**
 * 130. 被围绕的区域
 * https://leetcode-cn.com/problems/surrounded-regions/
 *
 * @author mizzle rain
 * @date 2020-12-23 15:04
 */
public class SurroundedRegions {
    // DFS 写法
    public void solve(char[][] board) {
        int h = board.length;
        if (h == 0) {
            return;
        }
        int w = board[0].length;
        if (w == 0) {
            return;
        }
        for (int i = 0; i < w; i++) {
            backTracking(board, 0, i);
            backTracking(board, h - 1, i);
        }
        for (int i = 0; i < h; i++) {
            backTracking(board, i, 0);
            backTracking(board, i, w - 1);
        }
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                if (board[i][j] == 'O') {
                    board[i][j] = 'X';
                }
                if (board[i][j] == '#') {
                    board[i][j] = 'O';
                }
            }
        }
    }

    private void backTracking(char[][] board, int i, int j) {
        int h = board.length;
        int w = board[0].length;
        if (i < 0 || j < 0 || i >= h || j >= w || board[i][j] != 'O') {
            return;
        }
        board[i][j] = '#';
        // 左方向
        backTracking(board, i - 1, j);
        // 右方向
        backTracking(board, i + 1, j);
        // 上方向
        backTracking(board, i, j - 1);
        // 下方向
        backTracking(board, i, j + 1);
    }

    @Test
    public void test1() {
        char[][] arr = {
                {'O', 'O'},
                {'O', 'O'},
        };
        new SurroundedRegions().solve(arr);
        Arrays.stream(arr).forEach(i -> System.out.println(Arrays.toString(i)));
    }

    @Test
    public void test2() {
        char[][] arr = {
                {'O', 'O', 'O'},
                {'O', 'O', 'O'},
                {'O', 'O', 'O'},
        };
        new SurroundedRegions().solve(arr);
        Arrays.stream(arr).forEach(i -> System.out.println(Arrays.toString(i)));
    }
}
